import java.util.*;
public class test {
    //leetcode 46.全排列
    class Solution {
        public List<List<Integer>> list;
        public List<Integer> path;
        public boolean[] count;
        public List<List<Integer>> permute(int[] nums) {
            //初始化
            //存储全排列结果
            list = new ArrayList<>();
            //存储单个全排列情况
            path = new ArrayList<>();
            //存储当前数字是否使用,用于剪枝
            count = new boolean[nums.length];
            dfs(nums);
            return list;
        }
        public void dfs(int[] nums){
            if(path.size() == nums.length){
                list.add(new ArrayList<>(path));
                return;
            }
            for(int i = 0;i < nums.length;i++){
                //该排列中该数字未被使用
                if(count[i] == false){
                    path.add(nums[i]);
                    count[i] = true;
                    dfs(nums);
                    //到此代表已将刚才的排列
                    //加入list中,此时开始回溯(恢复现场)
                    path.remove(path.size() - 1);
                    count[i] = false;
                }
            }
        }
    }
    //leetcode 47.全排列Ⅱ
    class Solution1 {
        public List<List<Integer>> list;
        public List<Integer> path;
        public HashSet<List<Integer>> set;
        public boolean[] count;

        public List<List<Integer>> permuteUnique(int[] nums) {
            list = new ArrayList<>();
            path = new ArrayList<>();
            set = new HashSet<>();
            count = new boolean[nums.length];
            // dfs(nums);
            // 使用剪枝判断此次排列中
            // 元素是否出现过时,如果扫描整个数组
            // 则复杂度过大,故先将数组进行排序,使相等的数相邻
            Arrays.sort(nums);
            // dfs1(nums);
            dfs2(nums);
            return list;
        }

        // 1. map存储法(低效率but易懂)
        public void dfs(int[] nums) {
            if (path.size() == nums.length && !set.contains(new ArrayList<>(path))) {
                list.add(new ArrayList<>(path));
                set.add(path);
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                if (count[i] == false) {
                    path.add(nums[i]);
                    count[i] = true;
                    dfs(nums);
                    path.remove(path.size() - 1);
                    count[i] = false;
                }
            }
        }

        // 2. 快速剪枝(只关心"合法"的分支)
        public void dfs1(int[] nums) {
            if (path.size() == nums.length) {
                list.add(new ArrayList<>(path));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                // 1. 当前元素未被使用(count[i] == false)
                // 2. 此次排列中,当前元素未被选取过(i == 0 或 nums[i - 1] != nums[i] 或 count[i - 1] ==
                // true(上个元素被使用过,直接跳过了))
                if (count[i] == false && (i == 0 || nums[i - 1] != nums[i] || count[i - 1])) {
                    path.add(nums[i]);
                    count[i] = true;
                    dfs1(nums);
                    path.remove(path.size() - 1);
                    count[i] = false;
                }
            }
        }

        // 3. 快速剪枝(只关心"不合法"的分支)
        public void dfs2(int[] nums) {
            if (path.size() == nums.length) {
                list.add(new ArrayList<>(path));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                // 1. 当前元素已经被使用
                // 2. 此次排列中,当前元素被选取过(排除count[i - 1] == false的情况,代表上个元素未被使用)
                if (!(count[i] == true || (i > 0 && (nums[i - 1] == nums[i] && count[i - 1] == false)))) {
                    path.add(nums[i]);
                    count[i] = true;
                    dfs2(nums);
                    path.remove(path.size() - 1);
                    count[i] = false;
                }
            }
        }
    }
}